package GreedyAlgorithm;

/**
 * 两个人轮流拿东西，谁能拿到最后一个
 *
 * @author Liaorun
 */
public class GetLastOne {

    public static String winner1(int n) {
        // 0  1  2 3  4
        // 后 先 后 先 先
        if (n < 5) {
            return (n == 0 || n == 2) ? "后手" : "先手";
        }

        // n >= 5时，先手决定吃的草
        int base = 1;
        // 有问题
        while (base <= n) {
            // 当前一共n份草，先手吃掉的是base份，n - base是留给后手的草4
            // 母过程是先手赢，在子过程里是 后手
            // 如果子过程告诉我后手能赢，那么一开始先手确实能赢
            if (winner1(n - base).equals("后手")) {
                return "先手";
            }

            // 防止base * 4之后溢出
            // 这一步还可以尝试吃更多的草
            if (base > n / 4) {
                break;
            }

            // 下一轮尝试吃更多的草
            base *= 4;
        }

        return "后手";
    }

    public static String winner2(int n) {
        if (n % 5 == 0 || n % 5 == 2) {
            return "后手";
        } else {
            return "先手";
        }
    }
}
